package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 最大子列和，及下标
 */
public class _63_2_MaxSubseqSum {
    public int maxSubsetSum(int[] numbs) {
        if (numbs == null) {
            return 0;
        }
        int thisSum = 0, maxSum = 0;
        int l = -1, r = -1;
        for (int i = 0; i < numbs.length; i++) {
            // 向右累加
            thisSum += numbs[i];
            if (l < 0) {
                l = i;
            }
            // 如果发现更大和则更新当前结果
            if (thisSum > maxSum) {
                maxSum = thisSum;
                r = i;
            }
            // 如果当前子列和为负，则不可能使后面的部分和增大，抛弃之
            else if (thisSum < 0) {
                thisSum = 0;
                l = -1;
            }
        }
        int[] index = new int[numbs.length];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }
        if (l > 0 && r>0){
            System.out.printf("[l, r] = [%d, %d]\n", numbs[l], numbs[r]);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        _63_2_MaxSubseqSum sum = new _63_2_MaxSubseqSum();
        int[] numbs = new int[]{-1, 3, -2, 4, -6, 1, 6, -1};
        test(sum, numbs);

        numbs = new int[]{-1, -3, -2, -4, -6, -1, -6, -1};
        test(sum, numbs);
    }

    private static void test(_63_2_MaxSubseqSum sum, int[] numbs) {
        System.out.println(Arrays.toString(numbs));
        System.out.println("最大子列和：" + sum.maxSubsetSum(numbs));
        System.out.println();
    }
}
